#include "stdio.h"
//希尔排序
//不断缩小“步长（gap）”，并对每个步长下的子序列执行插入排序。
//希尔排序时间复杂度是 O(n^(1.3-2))，空间复杂度为常数阶 O(1)
void Swap(int *a,int *b){
    int c=*a;
    *a = *b;
    *b = c;
}
void Print_Array(int *a,int n){
    printf("排序后的数组为:\r\n");
    for(int i=0;i<n;i++ ){
        printf("%d ",*a);
        a++;
    }
}

int main(){
    int array[9] = {0,1,2,3,4,5,6,7,8};
    int cnt = sizeof(array)/sizeof(array[0]);
    for(int n=cnt/2;n>0;n=n/2){
        for(int i=n;i<cnt;i+=n){
            for(int j=i;j>0;j-=n){
                if(array[j]>array[j-n]){
                    Swap(&array[j],&array[j-n]);
                }
                else{continue;}
            }
        }
    }
    Print_Array(array,cnt);
}